package com.mlh.linkedlist;

/**
 * @author 缪林辉
 * @date 2024/8/20 15:05
 * @DESCRIPTION
 */
// 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
public class 相交链表 {
    public static void main(String[] args) {
        ListNode headA=ListNode.createLinkedList(new int[]{4,1,8,4,5});
        ListNode headB=ListNode.createLinkedList(new int[]{5,6,1,8,4,5});
        ListNode listNode = method1(headA, headB);
    }
    public static ListNode method1(ListNode headA, ListNode headB) {
        ListNode temp=headA;
        int countA=0,countB=0;
        while (temp!=null){
            countA++;
            temp=temp.next;
        }
        temp=headB;
        while (temp!=null){
            countB++;
            temp=temp.next;
        }
        if(countA>countB){
            for (int i = 0; i < countA-countB; i++) {
                headA=headA.next;
            }
        }else {
            for (int i = 0; i < countB-countA; i++) {
                headB=headB.next;
            }
        }
        while(headA!=null&&headB!=null){
            if(headA==headB){
                return headA;
            }else {
                headA=headA.next;
                headB=headB.next;
            }
        }
        return null;
    }
    public static ListNode method2(ListNode headA, ListNode headB) {
        //上面通过计数的方式来消除长度差
        //这里通过：
        // 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
        // 如果 pA 到了末尾，则 pA = headB 继续遍历
        // 如果 pB 到了末尾，则 pB = headA 继续遍历
        // 比较长的链表指针指向较短链表head时，长度差就消除了
        if (headA == null || headB == null) return null;
        ListNode tempA=headA,tempB=headB;
        while (tempA!=tempB){
           tempA=tempA==null?headB:tempA.next;
           tempB=tempB==null?headA:tempB.next;
        }
        return tempA;
    }

    public static ListNode practice(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode tempA=headA,tempB=headB;
        while(tempA!=tempB){
            tempA=tempA==null?headB:tempA.next;
            tempB=tempB==null?headA:tempB.next;
        }
        return tempA;
    }

}
